{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Buildings With an Ocean View"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findBuildings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #能看到海景的建筑物"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有 <code>n</code> 座建筑物。给你一个大小为 <code>n</code> 的整数数组 <code>heights</code> 表示每一个建筑物的高度。</p>\n",
    "\n",
    "<p>建筑物的右边是海洋。如果建筑物可以无障碍地看到海洋，则建筑物能看到海景。确切地说，如果一座建筑物右边的所有建筑都比它 <strong>矮</strong> 时，就认为它能看到海景。</p>\n",
    "\n",
    "<p>返回能看到海景建筑物的下标列表（下标 <strong>从 <code>0</code> 开始</strong> ），并按升序排列。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>heights = [4,2,3,1]\n",
    "<strong>输出：</strong>[0,2,3]\n",
    "<strong>解释：</strong>1 号建筑物看不到海景，因为 2 号建筑物比它高\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>heights = [4,3,2,1]\n",
    "<strong>输出：</strong>[0,1,2,3]\n",
    "<strong>解释：</strong>所有的建筑物都能看到海景。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>heights = [1,3,2,4]\n",
    "<strong>输出：</strong>[3]\n",
    "<strong>解释：</strong>只有 3 号建筑物能看到海景。</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>heights = [2,2,2,2]\n",
    "<strong>输出：</strong>[3]\n",
    "<strong>解释：</strong>如果建筑物右边有相同高度的建筑物则无法看到海景。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= heights.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= heights[i] <= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [buildings-with-an-ocean-view](https://leetcode.cn/problems/buildings-with-an-ocean-view/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [buildings-with-an-ocean-view](https://leetcode.cn/problems/buildings-with-an-ocean-view/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,2,3,1]', '[4,3,2,1]', '[1,3,2,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "      maxHeight = -1\n",
    "      res = []\n",
    "      for i in range(len(heights) - 1, -1, -1):\n",
    "        if heights[i] > maxHeight:\n",
    "          res.append(i)\n",
    "          maxHeight = heights[i]\n",
    "      res.reverse()\n",
    "      return res\n",
    "      \n",
    "\n",
    "    def findBuildings1(self, heights: List[int]) -> List[int]:\n",
    "        if len(heights) == 0:\n",
    "          return []\n",
    "        if len(heights) == 1:\n",
    "          return [0]\n",
    "        prefix = [-1]\n",
    "        for i in range(len(heights) - 1, -1, -1):\n",
    "          prefix.append(max(prefix[-1], heights[i]))\n",
    "        prefix.reverse()\n",
    "        res = []\n",
    "        for i, h in enumerate(heights):\n",
    "          if h > prefix[i+1]:\n",
    "            res.append(i)\n",
    "        return res        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        res = [n-1]\n",
    "        max_h = 1\n",
    "        for idx in range(n-1, -1, -1):\n",
    "            if heights[idx] > max_h and idx<n-1:\n",
    "                res += [idx]\n",
    "            max_h = max(max_h, heights[idx])\n",
    "        return [res[idx] for idx in range(len(res)-1, -1, -1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        curMax = heights[-1]\n",
    "        i = len(heights) - 1\n",
    "        res.append(i)\n",
    "        i -= 1\n",
    "        for i in range(len(heights)-2,-1,-1):\n",
    "            if heights[i] > curMax:\n",
    "                res.append(i)\n",
    "                curMax = heights[i]\n",
    "            i -= 1\n",
    "        \n",
    "        return res[::-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        end = len(heights) - 1\n",
    "        point = len(heights) - 2\n",
    "        res = [end]\n",
    "        while point >= 0:\n",
    "            if heights[point] > heights[end]:\n",
    "                res.append(point)\n",
    "                end = point\n",
    "            point -= 1\n",
    "        return res[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        last_max = float('-inf')\n",
    "        res = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            val = heights[i]\n",
    "            if val > last_max:\n",
    "                # res.append(val) # wrong. index not val\n",
    "                res.append(i)\n",
    "                last_max = val\n",
    "        return res[::-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        max_h=float(\"-Inf\")\n",
    "        res=[]\n",
    "        for i in range(len(heights)-1,-1,-1):\n",
    "            if heights[i]>max_h:\n",
    "                res.append(i)\n",
    "                max_h=heights[i]\n",
    "        \n",
    "        return res[::-1]\n",
    "                \n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        res = [n-1]\n",
    "        max_h = heights[n-1]\n",
    "        for idx in range(n-2, -1, -1):\n",
    "            if heights[idx] > max_h:\n",
    "                res += [idx]\n",
    "            max_h = max(max_h, heights[idx])\n",
    "        return [res[idx] for idx in range(len(res)-1, -1, -1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        tallest = 0\n",
    "        res = []\n",
    "        for i in range(len(heights)-1, -1, -1):\n",
    "            if heights[i] > tallest:\n",
    "                res.append(i)\n",
    "                tallest = heights[i]\n",
    "\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        max_num = 0\n",
    "        l = len(heights) - 1 \n",
    "        res = []\n",
    "        for i in range(l, -1, -1):\n",
    "            if max_num < heights[i]:\n",
    "                res.append(i)\n",
    "                max_num = heights[i]\n",
    "        return res[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        max_h = 0\n",
    "        n = len(heights)\n",
    "        ans = []\n",
    "\n",
    "        for idx in range(n-1, -1, -1):\n",
    "            h = heights[idx]\n",
    "            if h > max_h:\n",
    "                ans.append(idx)\n",
    "            max_h = max(h, max_h)\n",
    "        \n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        n, result, cur_max = len(heights), [], 0\n",
    "        if n == 0: return result\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if heights[i] > cur_max:\n",
    "                result.append(i)\n",
    "                cur_max = heights[i]\n",
    "        result.reverse()\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        # if n == 1: # wrong since for [44], the res is 0 not [44]\n",
    "        #     return heights\n",
    "        res = []\n",
    "        max_val = -1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if heights[i] > max_val:\n",
    "                res.append(i)\n",
    "            max_val = max(max_val, heights[i])\n",
    "        return res[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "\n",
    "        line=[]\n",
    "\n",
    "        for idt in range(len(heights)-1,-1,-1):\n",
    "            if line==[]:\n",
    "                line.append(idt)\n",
    "            else:\n",
    "                node_h=heights[line[-1]]\n",
    "                if heights[idt]>node_h:\n",
    "                    line.append(idt)\n",
    "\n",
    "        return line[::-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        end = len(heights) - 1\n",
    "        point = len(heights) - 2\n",
    "        res = [end]\n",
    "        while point >= 0:\n",
    "            if heights[point] > heights[end]:\n",
    "                res.append(point)\n",
    "                end = point\n",
    "            point -= 1\n",
    "        res.sort()\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        curMax = heights[-1]\n",
    "        i = len(heights) - 1\n",
    "        res.append(i)\n",
    "        i -= 1\n",
    "        for i in range(len(heights)-2,-1,-1):\n",
    "            if heights[i] > curMax:\n",
    "                res.append(i)\n",
    "                curMax = heights[i]\n",
    "            i -= 1\n",
    "        \n",
    "        return res[::-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        ret = []\n",
    "        local_max = 0\n",
    "        for i in reversed(range(len(heights))):\n",
    "            if heights[i] > local_max:\n",
    "                local_max = heights[i]\n",
    "                ret.append(i)\n",
    "\n",
    "        return sorted(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # create a list of tallest building height from right side\n",
    "    # # if taller than threshold, add to res\n",
    "    # def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "    #     threshold_list = []\n",
    "    #     max_height = 0\n",
    "    #     for height in heights[::-1]:\n",
    "    #         threshold_list.append(max_height)\n",
    "    #         max_height = max(max_height, height)\n",
    "    #     res = []\n",
    "    #     cnt = len(heights)\n",
    "    #     for i, height in enumerate(heights):\n",
    "    #         if height > threshold_list[cnt - i - 1]:\n",
    "    #             res.append(i)\n",
    "    #     return res\n",
    "\n",
    "    # keep a variable of tallest building height from right side\n",
    "    # if taller than threshold, add to res\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        max_height = 0\n",
    "        res = []\n",
    "        cnt = len(heights)\n",
    "        for i, height in enumerate(heights[::-1]):\n",
    "            if height > max_height:\n",
    "                res.append(cnt - i - 1)\n",
    "            max_height = max(max_height, height)\n",
    "        res.reverse()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        #等价于从当前起点开始往右找第一个大于当前值的点，若没有则说明能看到海景,便于计算我们设置一个哨兵节点，省去特判的过程\n",
    "        n=len(heights)\n",
    "        stack,ans=[n],[]\n",
    "        heights.append(inf)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while heights[i]>heights[stack[-1]]:\n",
    "                stack.pop()\n",
    "            if stack[-1]==n: ans.append(i)\n",
    "            stack.append(i)\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        res = []\n",
    "        for i in range(len(heights)-1, -1, -1):\n",
    "            if stack and stack[-1] < heights[i]:\n",
    "                stack.append(heights[i])\n",
    "                res.append(i)\n",
    "            elif not stack:\n",
    "                stack.append(heights[i])\n",
    "                res.append(i)\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        max_h = 0\n",
    "        res = []\n",
    "        for i in range(len(heights) - 1, -1, -1):\n",
    "            if heights[i] > max_h:\n",
    "                res.append(i)\n",
    "                max_h = heights[i]\n",
    "        return res[::-1]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, h: List[int]) -> List[int]:\n",
    "        n = len(h)\n",
    "        ans = [n-1]\n",
    "        tmp = h[n-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if h[i] > tmp:\n",
    "                ans.append(i)\n",
    "                tmp = h[i]\n",
    "        return ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        '''\n",
    "        能看到海景，则其比之后的数字都大\n",
    "        从右往左遍历\n",
    "        '''\n",
    "        n = len(heights)\n",
    "        ans = [n-1] # 最右建筑一定能看到\n",
    "        \n",
    "        tmp = heights[n-1] # tmp记录最大值\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if heights[i] > tmp:\n",
    "                ans.append(i)\n",
    "                tmp = heights[i]\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        max_height = 0\n",
    "        results = []\n",
    "        for i in range(len(heights) - 1, -1, -1):\n",
    "            if heights[i] > max_height:\n",
    "                results.append(i)\n",
    "            max_height = max(max_height, heights[i])\n",
    "\n",
    "        return results[::-1]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        l = len(heights)\n",
    "        max_height = -float('INF')\n",
    "        ans = []\n",
    "        for i in range(l-1, -1, -1):\n",
    "            if heights[i] > max_height:\n",
    "                ans.append(i)\n",
    "                max_height = heights[i]\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        # scan from right to left, keep tracking highest building\n",
    "        res = []\n",
    "        highest = 0\n",
    "\n",
    "        for i in range(len(heights)-1, -1, -1):\n",
    "            if heights[i] > highest:\n",
    "                res.append(i)\n",
    "                highest = heights[i]\n",
    "        return res[::-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "\n",
    "        max_ = -float(\"INF\")\n",
    "        res = []\n",
    "        for i,h in enumerate(heights[::-1]):\n",
    "            if h>max_:\n",
    "                res.append(len(heights)-1-i)\n",
    "            max_ = max(h,max_)\n",
    "        \n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        if len(heights) == 0:\n",
    "            return []\n",
    "        if len(heights) == 1:\n",
    "            return [0]\n",
    "            \n",
    "\n",
    "        heights = heights[::-1] # to the left\n",
    "\n",
    "        pre_max_height = 0 # register before heights[i] the max_height\n",
    "\n",
    "        res = []\n",
    "\n",
    "        for i, height in enumerate(heights):\n",
    "            if height > pre_max_height:\n",
    "                res.append(len(heights)-1-i)\n",
    "                pre_max_height = max(pre_max_height, height)\n",
    "            \n",
    "        # out = []\n",
    "        # for item in res:\n",
    "        #     out.append(len(heights)-1 - item)\n",
    "        # return sorted(out)\n",
    "        return sorted(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        ans = [n - 1]\n",
    "        now = heights[-1]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if heights[i] > now:\n",
    "                ans.append(i)\n",
    "            now = max(heights[i], now)\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        ans = [n - 1]\n",
    "        now = heights[-1]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if heights[i] > now:\n",
    "                ans.append(i)\n",
    "            now = max(heights[i], now)\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        if not heights or len(heights) == 0:\n",
    "            return heights\n",
    "        \n",
    "        marks = [0]* len(heights)\n",
    "        tmp_max = -1\n",
    "        \n",
    "        for i in range(len(heights)-2, -1, -1):\n",
    "            tmp_max = max(heights[i+1], tmp_max)\n",
    "            marks[i] = tmp_max\n",
    "        \n",
    "        res = []\n",
    "        # print(f'marks = {marks}')\n",
    "        # print(f'heights = {heights}')\n",
    "\n",
    "        for i in range(len(heights)):\n",
    "            if heights[i] > marks[i]:\n",
    "                res.append(i)\n",
    "            \n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        res = []\n",
    "        for i in range(len(heights)-1, -1, -1):\n",
    "            if stack and heights[i] <= stack[-1]:\n",
    "                continue\n",
    "            stack.append(heights[i])\n",
    "            res.append(i)\n",
    "\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        suf = -inf\n",
    "        for i in range(len(heights)-1, -1, -1):\n",
    "            if heights[i] > suf:\n",
    "                ans.append(i)\n",
    "            suf = max(suf, heights[i])\n",
    "        ans.reverse()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        # if n == 1: # wrong since for [44], the res is 0 not [44]\n",
    "        #     return heights\n",
    "        res = []\n",
    "        max_val = -1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if heights[i] > max_val:\n",
    "                res.append(i)\n",
    "            max_val = max(max_val, heights[i])\n",
    "        return res[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        rightMax = 0\n",
    "        n = len(heights)\n",
    "        res = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if heights[i] > rightMax:\n",
    "                res.append(i)\n",
    "                rightMax = heights[i]\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        if not heights:\n",
    "            return []\n",
    "        max_height = 0\n",
    "        has_oceanview = []\n",
    "        for i in range(len(heights) - 1, -1, -1):\n",
    "            if heights[i] > max_height:\n",
    "                has_oceanview.append(i)\n",
    "            max_height = max(max_height, heights[i])\n",
    "        has_oceanview.reverse()\n",
    "        return has_oceanview"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        res = []\n",
    "        for i in range(len(heights)-1, -1, -1):\n",
    "            if not stack or (stack and heights[i] > stack[-1]):\n",
    "                stack.append(heights[i])\n",
    "                res.append(i)\n",
    "\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        output = []\n",
    "        max_height_cur = 1\n",
    "        for i in range(len(heights)-1, 0, -1):\n",
    "            if heights[i] > max_height_cur: \n",
    "                max_height_cur = heights[i]\n",
    "            res.append(max_height_cur)\n",
    "        res.reverse()\n",
    "        for j in range(len(heights)-1):\n",
    "            if heights[j]> res[j]:\n",
    "                output.append(j)\n",
    "        output.append(len(heights)-1)\n",
    "        return output\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        max_height = -1  # 初始化最高建筑物的高度\n",
    "        result = []  # 初始化结果列表\n",
    "\n",
    "        # 从右到左遍历建筑物\n",
    "        for i in reversed(range(len(heights))):\n",
    "            # 如果当前建筑物的高度大于目前为止的最高建筑物\n",
    "            if heights[i] > max_height:\n",
    "                # 添加这个建筑物的下标到结果列表\n",
    "                result.append(i)\n",
    "                # 更新最高建筑物的高度\n",
    "                max_height = heights[i]\n",
    "\n",
    "        # 因为我们是从右到左遍历的，所以需要反转结果列表以得到升序的下标\n",
    "        return list(reversed(result))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # create a list of tallest building height from right side\n",
    "    # if taller than threshold, add to res\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        threshold_list = []\n",
    "        max_height = 0\n",
    "        for height in heights[::-1]:\n",
    "            threshold_list.append(max_height)\n",
    "            max_height = max(max_height, height)\n",
    "        threshold_list.reverse()\n",
    "        res = []\n",
    "        for i, height in enumerate(heights):\n",
    "            if height > threshold_list[i]:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # create a list of tallest building height from right side\n",
    "    # if taller than threshold, add to res\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        reverse_threshold_list = []\n",
    "        max_height = 0\n",
    "        for height in heights[::-1]:\n",
    "            reverse_threshold_list.append(max_height)\n",
    "            max_height = max(max_height, height)\n",
    "        reverse_threshold_list.reverse()\n",
    "        threshold_list = reverse_threshold_list\n",
    "        res = []\n",
    "        for i, height in enumerate(heights):\n",
    "            if height > threshold_list[i]:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # create a list of tallest building height from right side\n",
    "    # if taller than threshold, add to res\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        threshold_list = []\n",
    "        max_height = 0\n",
    "        for height in heights[::-1]:\n",
    "            threshold_list.append(max_height)\n",
    "            max_height = max(max_height, height)\n",
    "        res = []\n",
    "        cnt = len(heights)\n",
    "        for i, height in enumerate(heights):\n",
    "            if height > threshold_list[cnt - i - 1]:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        #单调栈解法,维护一个单调递减的栈\n",
    "        #题目意思是找到数组右边不存在大于它的值的节点\n",
    "        #那我们反向考虑把找到的抛出,单调栈中存储还没有找到右边不存在大于它的值的节点,遍历完数组就得到答案了。\n",
    "        st=[]\n",
    "        for i in range(len(heights)):\n",
    "            while st and heights[i]>=heights[st[-1]]:\n",
    "                st.pop()\n",
    "            st.append(i)\n",
    "        return st"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        n = len(heights)\n",
    "\n",
    "        for i, height in enumerate(heights):\n",
    "            while stack and height >= heights[stack[-1]]:\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        \n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        n = len(heights)\n",
    "        for i in range(n):\n",
    "            while stack and heights[stack[-1]] <= heights[i]:\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        stack = list()\n",
    "        for index, val in enumerate(heights):\n",
    "            while stack and heights[stack[-1]] <= val:\n",
    "                stack.pop()\n",
    "            stack.append(index)\n",
    "                \n",
    "\n",
    "        return stack\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        stack = []\n",
    "        n = len(heights)\n",
    "\n",
    "        for i in range(n):\n",
    "            while stack and heights[i] >= heights[stack[-1]]:\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        \n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        stack = []\n",
    "\n",
    "        for i in range(n):\n",
    "            while stack and heights[stack[-1]] <= heights[i]:\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return list(stack) \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        s = []\n",
    "        for i, h in enumerate(heights):\n",
    "            while len(s) > 0 and h >= heights[s[-1]]:\n",
    "                s.pop()\n",
    "            else:\n",
    "                s.append(i)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        stack = [0]\n",
    "        n = len(heights)\n",
    "\n",
    "        for i in range(1, n):\n",
    "            while stack and heights[i]>=heights[stack[-1]]:\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        ret = []\n",
    "        for i in reversed(range(len(heights))):\n",
    "            while stack and heights[stack[-1]] < heights[i]:\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "            if stack[0] == i:\n",
    "                ret.append(i)\n",
    "        return ret[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        \n",
    "        index = []\n",
    "        stack = []\n",
    "        for i in range(len(heights)):\n",
    "            if not stack:\n",
    "                stack.append(heights[i])\n",
    "                index.append(i)\n",
    "                continue \n",
    "            while stack:\n",
    "                x = stack[-1]\n",
    "                y = heights[i]\n",
    "                if y>=x:\n",
    "                    stack.pop()\n",
    "                    index.pop()\n",
    "                else:\n",
    "                    break \n",
    "            stack.append(heights[i])\n",
    "            index.append(i)\n",
    "        return index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        if not heights or len(heights) == 0:\n",
    "            return heights\n",
    "        \n",
    "\n",
    "        marks = [0]* len(heights)\n",
    "        tmp_max = -1\n",
    "        \n",
    "        for i in range(len(heights)-2, -1, -1):\n",
    "            tmp_max = max(heights[i+1], tmp_max)\n",
    "            marks[i] = tmp_max\n",
    "        \n",
    "        # marks[0] = tmp_max\n",
    "        # [51,78]\n",
    "        # [-1, 0]\n",
    "        # [78, 0]\n",
    "        res = []\n",
    "        print(f'marks = {marks}')\n",
    "        print(f'heights = {heights}')\n",
    "\n",
    "        for i in range(len(heights)):\n",
    "            if heights[i] > marks[i]:\n",
    "                res.append(i)\n",
    "            \n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "\n",
    "        stk = []\n",
    "\n",
    "        for i in range(len(heights)):\n",
    "\n",
    "            while stk and heights[i] >= heights[stk[-1]]:\n",
    "                stk.pop()\n",
    "            stk.append(i)\n",
    "        return stk "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        n = len(heights)\n",
    "        for i in range(n):\n",
    "            while stack and heights[stack[-1]] <= heights[i]:\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        stack = [0]\n",
    "        n = len(heights)\n",
    "\n",
    "        for i in range(1, n):\n",
    "            while stack and heights[i]>=heights[stack[-1]]:\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        stack = [] # idex\n",
    "        for idx, h in enumerate(heights):\n",
    "            while stack and heights[stack[-1]] <= h:\n",
    "                stack.pop()\n",
    "            \n",
    "            stack.append(idx)\n",
    "\n",
    "        return stack\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        n = len(heights)\n",
    "        if n == 1:\n",
    "            return [0]\n",
    "        stack.append(0)\n",
    "        for i in range(1, n):\n",
    "            while stack and heights[stack[-1]] <= heights[i]:\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return stack\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        stack=[]\n",
    "        for k,v in enumerate(heights):\n",
    "            while stack!=[] and heights[stack[-1]]<=heights[k]:\n",
    "                stack.pop()\n",
    "            stack.append(k)\n",
    "        return stack\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        from sortedcontainers import SortedList\n",
    "        sl = SortedList()\n",
    "        res = []\n",
    "\n",
    "        for i in range(len(heights) - 1, -1, -1):\n",
    "            j =  sl.bisect_left(heights[i])\n",
    "            if j == len(sl):\n",
    "                res.append(i)\n",
    "            sl.add(heights[i])\n",
    "        \n",
    "        return list(reversed(res))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        max_num = 0\n",
    "        l = len(heights) - 1 \n",
    "        res = []\n",
    "        for ind, value in enumerate(heights[::-1]):\n",
    "            if value > max_num:\n",
    "                res.append(ind)\n",
    "                max_num = value\n",
    "        return sorted([l - x for x in res])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBuildings(self, heights: List[int]) -> List[int]:\n",
    "        max_num = 0\n",
    "        l = len(heights) - 1 \n",
    "        res = []\n",
    "        for ind, value in enumerate(heights[::-1]):\n",
    "            if value > max_num:\n",
    "                res.append(ind)\n",
    "                max_num = value\n",
    "        return [l - x for x in res][::-1]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
